package com.leetcode.No0496;

import org.junit.Test;

import java.util.*;

/**
 * @program: Solution
 * @description: 下一个更大元素 I
 * @author: Wang Zhihua
 * @date: 2022-11-01
 */
public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>(nums1.length);

        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, (stack.peek() == null ? -1 : stack.peek()));
            stack.push(num);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }

    @Test
    public void test01() {
        int[] nums1, nums2;

        nums1 = new int[]{4,1,2};
        nums2 = new int[]{1,3,4,2};
        System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));

        nums1 = new int[]{2,4};
        nums2 = new int[]{1,2,3,4};
        System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));
    }
}
